package leetcode.editor.week.week306;

// 2375. 根据模式串构造最小数字
// https://leetcode.cn/problems/construct-smallest-number-from-di-string/
public class Solution6150 {
    // https://leetcode.cn/problems/construct-smallest-number-from-di-string/solution/by-endlesscheng-8ee3/
    public String smallestNumber(String pattern) {
        int i = 0, n = pattern.length();
        char cur = '1';
        char[] ans = new char[n + 1];
        while (i < n) {
            // 中间出现I，已经被上一个D填充
            if (i > 0 && pattern.charAt(i) == 'I') i++;
            // 填充I
            for (; i < n && pattern.charAt(i) == 'I'; i++) ans[i] = cur++;
            int i0 = i;
            while (i < n && pattern.charAt(i) == 'D') i++;
            // 填充D，注意把D后面一位都填了
            for (int j = i; j >= i0; j--) ans[j] = cur++;
        }

        return new String(ans);
    }
}
